'''
BM7 链表中环的入口结点
'''

class ListNode:
    def __init__(self,val,next=None):
        self.val = val
        self.next = next

class Solution:

    def hasCycle(self,head:ListNode):
        if head == None:
            return None
        fast = head
        slow = head

        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return slow

        return None

    def EntryNodeOfLoop(self,head:ListNode):
        entry = self.hasCycle(head)
        if entry == None:
            return None

        slow = entry
        fast = head

        while fast != slow:
            fast = fast.next
            slow = slow.next
        return slow


if __name__ == "__main__":
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node2

    solution = Solution()
    print(solution.EntryNodeOfLoop(node1).val)